SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Interior-point method</title>

</head>

Interior-point method

</h1>

</header>

Interior-point methods (also referred to as barrier methods or IPMs) are <a href="Algorithm" title="Algorithm">algorithms</a> for solving <a href="Linear_programming" title="Linear programming">linear</a> and <a href="Nonlinear_programming" title="Nonlinear programming">non-linear</a> <a href="Convex_optimization" title="Convex optimization">convex optimization</a> problems. IPMs combine two advantages of previously-known algorithms:

<ul><li>Theoretically, their run-time is <a href="Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial</a>—in contrast to the <a href="Simplex_method" class="mw-redirect" title="Simplex method">simplex method</a>, which has exponential run-time in the worst case.</li>

<li>Practically, they run as fast as the simplex method—in contrast to the <a href="Ellipsoid_method" title="Ellipsoid method">ellipsoid method</a>, which has polynomial run-time in theory but is very slow in practice.</li></ul>

In contrast to the simplex method which traverses the boundary of the feasible region, and the ellipsoid method which bounds the feasible region from outside, an IPM reaches a best solution by traversing the interior of the <a href="Feasible_region" title="Feasible region">feasible region</a>—hence the name.

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

An interior point method was discovered by Soviet mathematician I. I. Dikin in 1967.<a href="#cite_note-1">[1]</a> The method was reinvented in the U.S. in the mid-1980s. In 1984, <a href="Narendra_Karmarkar" title="Narendra Karmarkar">Narendra Karmarkar</a> developed a method for <a href="Linear_programming" title="Linear programming">linear programming</a> called <a href="Karmarkar's_algorithm" title="Karmarkar's algorithm">Karmarkar's algorithm</a>,<a href="#cite_note-2">[2]</a> which runs in probably polynomial time (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{3.5}L)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{3.5}L)}</annotation>

</semantics>

</math><img src="./75bfa3b481f545e25ae3d8d60ef6ca14d51050ef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.894ex; height:3.176ex;" alt="{\displaystyle O(n^{3.5}L)}" loading="lazy"> operations on L-bit numbers, where n is the number of variables and constants), and is also very efficient in practice. Karmarkar's paper created a surge of interest in interior point methods. Two years later, <a href="James_Renegar" title="James Renegar">James Renegar</a> invented the first path-following interior-point method, with run-time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{3}L)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{3}L)}</annotation>

</semantics>

</math><img src="./4196dab2e7e34d3a1c8ddf3b622884fc5923f6c8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.614ex; height:3.176ex;" alt="{\displaystyle O(n^{3}L)}" loading="lazy">. The method was later extended from linear to convex optimization problems, based on a <a href="Self-concordant" class="mw-redirect" title="Self-concordant">self-concordant</a> <a href="Barrier_function" title="Barrier function">barrier function</a> used to encode the <a href="Convex_set" title="Convex set">convex set</a>.<a href="#cite_note-:0-3">[3]</a>

Any convex optimization problem can be transformed into minimizing (or maximizing) a <a href="Linear_function" title="Linear function">linear function</a> over a convex set by converting to the <a href="Epigraph_(mathematics)" title="Epigraph (mathematics)">epigraph</a> form.<a href="#cite_note-:3-4">[4]</a>: 143 The idea of encoding the <a href="Candidate_solution" class="mw-redirect" title="Candidate solution">feasible set</a> using a barrier and designing barrier methods was studied by Anthony V. Fiacco, Garth P. McCormick, and others in the early 1960s. These ideas were mainly developed for general <a href="Nonlinear_programming" title="Nonlinear programming">nonlinear programming</a>, but they were later abandoned due to the presence of more competitive methods for this class of problems (e.g. <a href="Sequential_quadratic_programming" title="Sequential quadratic programming">sequential quadratic programming</a>).

<a href="Yurii_Nesterov" title="Yurii Nesterov">Yurii Nesterov</a> and <a href="Arkadi_Nemirovski" title="Arkadi Nemirovski">Arkadi Nemirovski</a> came up with a special class of such barriers that can be used to encode any convex set. They guarantee that the number of <a href="Iteration" title="Iteration">iterations</a> of the algorithm is bounded by a polynomial in the dimension and accuracy of the solution.<a href="#cite_note-5">[5]</a><a href="#cite_note-:0-3">[3]</a>

The class of primal-dual path-following interior-point methods is considered the most successful. <a href="Mehrotra_predictor%E2%80%93corrector_method" title="Mehrotra predictor–corrector method">Mehrotra's predictor–corrector algorithm</a> provides the basis for most implementations of this class of methods.<a href="#cite_note-6">[6]</a>

<div class="mw-heading mw-heading2"><h2 id="Definitions">Definitions</h2></div>

We are given a <a href="Convex_program" class="mw-redirect" title="Convex program">convex program</a> of the form:<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{minimize}}}\quad &f(x)\\{\text{subject to}}\quad &x\in G.\end{aligned}}}">

<mtr>

<mtd>

<mtext>minimize</mtext>

<mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{minimize}}}\quad &f(x)\\{\text{subject to}}\quad &x\in G.\end{aligned}}}</annotation>

</semantics>

</math>where f is a <a href="Convex_function" title="Convex function">convex function</a> and G is a <a href="Convex_set" title="Convex set">convex set</a>. Without loss of generality, <a href="Convex_optimization#linear" title="Convex optimization">we can assume that the objective f is a linear function</a>. Usually, the convex set G is represented by a set of convex inequalities and linear equalities; the linear equalities can be eliminated using linear algebra, so for simplicity we assume there are only convex inequalities, and the program can be described as follows, where the gi are convex functions:<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{minimize}}}\quad &f(x)\\{\text{subject to}}\quad &g_{i}(x)\leq 0{\text{ for }}i=1,\dots ,m.\\\end{aligned}}}">

<mtr>

<mtd>

<mtext>minimize</mtext>

<mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{minimize}}}\quad &f(x)\\{\text{subject to}}\quad &g_{i}(x)\leq 0{\text{ for }}i=1,\dots ,m.\\\end{aligned}}}</annotation>

</semantics>

</math>We assume that the constraint functions belong to some family (e.g. quadratic functions), so that the program can be represented by a finite vector of coefficients (e.g. the coefficients to the quadratic functions). The dimension of this coefficient vector is called the size of the program. A numerical solver for a given family of programs is an algorithm that, given the coefficient vector, generates a sequence of approximate solutions xt for t=1,2,..., using finitely many arithmetic operations. A numerical solver is called convergent if, for any program from the family and any positive ε>0, there is some T (which may depend on the program and on ε) such that, for any t>T, the approximate solution xt is ε-approximate, that is:<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}&f(x_{t})-f^{*}\leq \epsilon ,\\&g_{i}(x_{t})\leq \epsilon \quad {\text{for}}\quad i=1,\dots ,m,\\&x\in G,\end{aligned}}}">

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&f(x_{t})-f^{*}\leq \epsilon ,\\&g_{i}(x_{t})\leq \epsilon \quad {\text{for}}\quad i=1,\dots ,m,\\&x\in G,\end{aligned}}}</annotation>

</semantics>

</math>where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f^{*}}</annotation>

</semantics>

</math><img src="./190a73fde235865b8d2a783334f90194331c7f19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.375ex; height:2.676ex;" alt="{\displaystyle f^{*}}" loading="lazy"> is the optimal solution. A solver is called polynomial if the total number of arithmetic operations in the first T steps is at most<blockquote>poly(problem-size) * log(V/ε),</blockquote>where V is some data-dependent constant, e.g., the difference between the largest and smallest value in the feasible set. In other words, V/ε is the "relative accuracy" of the solution - the accuracy w.r.t. the largest coefficient. log(V/ε) represents the number of "accuracy digits". Therefore, a solver is 'polynomial' if each additional digit of accuracy requires a number of operations that is polynomial in the problem size.

<div class="mw-heading mw-heading2"><h2 id="Types">Types</h2></div>

Types of interior point methods include:

<ul><li>Potential reduction methods: <a href="Karmarkar_algorithm" class="mw-redirect" title="Karmarkar algorithm">Karmarkar's algorithm</a> was the first one.</li>

<li>Path-following methods: the algorithms of <a href="James_Renegar" title="James Renegar">James Renegar</a><a href="#cite_note-:1-7">[7]</a> and Clovis Gonzaga<a href="#cite_note-:2-8">[8]</a> were the first ones.</li>

<li>Primal-dual methods.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Path-following_methods">Path-following methods</h2></div>

Given a convex optimization program (P) with constraints, we can convert it to an unconstrained program by adding a <a href="Barrier_function" title="Barrier function">barrier function</a>. Specifically, let b be a smooth convex function, defined in the interior of the feasible region G, such that for any sequence {xj in interior(G)} whose limit is on the boundary of G: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lim _{j\to \infty }b(x_{j})=\infty }">

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lim _{j\to \infty }b(x_{j})=\infty }</annotation>

</semantics>

</math><img src="./1eec7331488abd8fbea4f63240f43ac35fd2d445.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; margin-left: -0.019ex; width:14.838ex; height:4.343ex;" alt="{\displaystyle \lim _{j\to \infty }b(x_{j})=\infty }" loading="lazy">. We also assume that b is non-degenerate, that is: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b''(x)}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b''(x)}</annotation>

</semantics>

</math><img src="./7496d7ba75c1ae6b14309a4f1c9cf855f4364f75.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.274ex; height:3.009ex;" alt="{\displaystyle b''(x)}" loading="lazy"> is <a href="Positive-definite_function" title="Positive-definite function">positive definite</a> for all x in interior(G). Now, consider the family of programs:<blockquote>(Pt) minimize t * f(x) + b(x)</blockquote>Technically the program is restricted, since b is defined only in the interior of G. But practically, it is possible to solve it as an unconstrained program, since any solver trying to minimize the function will not approach the boundary, where b approaches infinity. Therefore, (Pt) has a unique solution - denote it by x*(t). The function x* is a continuous function of t, which is called the central path. All limit points of x*, as t approaches infinity, are optimal solutions of the original program (P).

A path-following method is a method of tracking the function x* along a certain increasing sequence t1,t2,..., that is: computing a good-enough approximation xi to the point x*(ti), such that the difference xi - x*(ti) approaches 0 as i approaches infinity; then the sequence xi approaches the optimal solution of (P). This requires to specify three things:

<ul><li>The barrier function b(x).</li>

<li>A policy for determining the penalty parameters ti.</li>

<li>The unconstrained-optimization solver used to solve (Pi) and find xi, such as <a href="Newton's_method" title="Newton's method">Newton's method</a>. Note that we can use each xi as a starting-point for solving the next problem (Pi+1).</li></ul>

The main challenge in proving that the method is polytime is that, as the penalty parameter grows, the solution gets near the boundary, and the function becomes steeper. The run-time of solvers such as <a href="Newton's_method" title="Newton's method">Newton's method</a> becomes longer, and it is hard to prove that the total runtime is polynomial.

Renegar<a href="#cite_note-:1-7">[7]</a> and Gonzaga<a href="#cite_note-:2-8">[8]</a> proved that a specific instance of a path-following method is polytime:

<ul><li>The constraints (and the objective) are linear functions;</li>

<li>The barrier function is <a href="Logarithmic_barrier_function" class="mw-redirect" title="Logarithmic barrier function">logarithmic</a>: b(x) := - sumj log(-gj(x)).</li>

<li>The penalty parameter t is updated geometrically, that is, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t_{i+1}:=\mu \cdot t_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t_{i+1}:=\mu \cdot t_{i}}</annotation>

</semantics>

</math><img src="./4784c909691411ec0795808e0ab9d03b7a6b4272.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.205ex; height:2.509ex;" alt="{\displaystyle t_{i+1}:=\mu \cdot t_{i}}" loading="lazy">, where μ is a constant (they took <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu =1+0.001\cdot {\sqrt {m}}}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu =1+0.001\cdot {\sqrt {m}}}</annotation>

</semantics>

</math><img src="./266cecf4def33dbf652c7abd5371fad56aafcb90.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:19.455ex; height:3.009ex;" alt="{\displaystyle \mu =1+0.001\cdot {\sqrt {m}}}" loading="lazy">, where m is the number of inequality constraints);</li>

<li>The solver is Newton's method, and a single step of Newton is done for each single step in t.</li></ul>

They proved that, in this case, the difference xi - x*(ti) remains at most 0.01, and f(xi) - f* is at most 2*m/ti. Thus, the solution accuracy is proportional to 1/ti, so to add a single accuracy-digit, it is sufficient to multiply ti by 2 (or any other constant factor), which requires O(sqrt(m)) Newton steps. Since each Newton step takes O(m n2) operations, the total complexity is O(m3/2 n2) operations for accuracy digit.

<a href="Yurii_Nesterov" title="Yurii Nesterov">Yuri Nesterov</a> extended the idea from linear to non-linear programs. He noted that the main property of the logarithmic barrier, used in the above proofs, is that it is <a href="Self-concordant" class="mw-redirect" title="Self-concordant">self-concordant</a> with a finite barrier parameter. Therefore, many other classes of convex programs can be solved in polytime using a path-following method, if we can find a suitable self-concordant barrier function for their feasible region.<a href="#cite_note-:0-3">[3]</a>: Sec.1

<div class="mw-heading mw-heading3"><h3 id="Details">Details</h3></div>

We are given a convex optimization problem (P) in "standard form":<blockquote>minimize cTx s.t. x in G, </blockquote>where G is convex and closed. We can also assume that G is bounded (we can easily make it bounded by adding a constraint |x|≤R for some sufficiently large R).<a href="#cite_note-:0-3">[3]</a>: Sec.4

To use the interior-point method, we need a <a href="Self-concordant_barrier" class="mw-redirect" title="Self-concordant barrier">self-concordant barrier</a> for G. Let b be an M-self-concordant barrier for G, where M≥1 is the self-concordance parameter. We assume that we can compute efficiently the value of b, its gradient, and its <a href="Hessian_matrix" title="Hessian matrix">Hessian</a>, for every point x in the interior of G.

For every t>0, we define the penalized objective ft(x) := tcTx + b(x). We define the path of minimizers by: x*(t) := arg min ft(x). We approximate this path along an increasing sequence ti. The sequence is initialized by a certain non-trivial two-phase initialization procedure. Then, it is updated according to the following rule: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t_{i+1}:=\mu \cdot t_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t_{i+1}:=\mu \cdot t_{i}}</annotation>

</semantics>

</math><img src="./4784c909691411ec0795808e0ab9d03b7a6b4272.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.205ex; height:2.509ex;" alt="{\displaystyle t_{i+1}:=\mu \cdot t_{i}}" loading="lazy">.

For each ti, we find an approximate minimum of fti, denoted by xi. The approximate minimum is chosen to satisfy the following "closeness condition" (where L is the path tolerance):<blockquote><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\sqrt {[\nabla _{x}f_{t}(x_{i})]^{T}[\nabla _{x}^{2}f_{t}(x_{i})]^{-1}[\nabla _{x}f_{t}(x_{i})]}}\leq L}">

<msqrt>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\sqrt {[\nabla _{x}f_{t}(x_{i})]^{T}[\nabla _{x}^{2}f_{t}(x_{i})]^{-1}[\nabla _{x}f_{t}(x_{i})]}}\leq L}</annotation>

</semantics>

</math><img src="./f1c487615f788974227a6e9b97a12c1b9ba72038.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.671ex; width:41.645ex; height:4.843ex;" alt="{\displaystyle {\sqrt {[\nabla _{x}f_{t}(x_{i})]^{T}[\nabla _{x}^{2}f_{t}(x_{i})]^{-1}[\nabla _{x}f_{t}(x_{i})]}}\leq L}" loading="lazy">.</blockquote>To find xi+1, we start with xi and apply the <a href="Damped_Newton_method" class="mw-redirect" title="Damped Newton method">damped Newton method</a>. We apply several steps of this method, until the above "closeness relation" is satisfied. The first point that satisfies this relation is denoted by xi+1.<a href="#cite_note-:0-3">[3]</a>: Sec.4

<div class="mw-heading mw-heading3"><h3 id="Convergence_and_complexity">Convergence and complexity</h3></div>

The convergence rate of the method is given by the following formula, for every i:<a href="#cite_note-:0-3">[3]</a>: Prop.4.4.1 <blockquote><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c^{T}x_{i}-c^{*}\leq {\frac {2M}{t_{0}}}\mu ^{-i}}">

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<mfrac>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c^{T}x_{i}-c^{*}\leq {\frac {2M}{t_{0}}}\mu ^{-i}}</annotation>

</semantics>

</math><img src="./6e114e95aa8659b01e7f9dfe81c73cd141b1d25a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:20.446ex; height:5.509ex;" alt="{\displaystyle c^{T}x_{i}-c^{*}\leq {\frac {2M}{t_{0}}}\mu ^{-i}}" loading="lazy"></blockquote>Taking <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu =\left(1+r/{\sqrt {M}}\right)}">

<mrow>

<mrow>

</mrow>

<msqrt>

</msqrt>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu =\left(1+r/{\sqrt {M}}\right)}</annotation>

</semantics>

</math><img src="./0e77066a7e3c95b14146a108b36b2616e251ab31.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:17.222ex; height:3.343ex;" alt="{\displaystyle \mu =\left(1+r/{\sqrt {M}}\right)}" loading="lazy">, the number of Newton steps required to go from xi to xi+1 is at most a fixed number, that depends only on r and L. In particular, the total number of Newton steps required to find an ε-approximate solution (i.e., finding x in G such that cTx - c* ≤ ε) is at most:<a href="#cite_note-:0-3">[3]</a>: Thm.4.4.1 <blockquote><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M}{t_{0}\varepsilon }}+1\right)}">

<msqrt>

</msqrt>

</mrow>

<mrow>

<mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M}{t_{0}\varepsilon }}+1\right)}</annotation>

</semantics>

</math><img src="./07ba075b02deef5401eb45b5343e45d6deb4b5e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:25.658ex; height:6.176ex;" alt="{\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M}{t_{0}\varepsilon }}+1\right)}" loading="lazy"></blockquote>where the constant factor O(1) depends only on r and L. The number of Newton steps required for the two-step initialization procedure is at most:<a href="#cite_note-:0-3">[3]</a>: Thm.4.5.1 <blockquote><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M}{1-\pi _{x_{f}^{*}}({\bar {x}})}}+1\right)+O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M{\text{Var}}_{G}(c)}{\epsilon }}+1\right)}">

<msqrt>

</msqrt>

</mrow>

<mrow>

<mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

<msqrt>

</msqrt>

</mrow>

<mrow>

<mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M}{1-\pi _{x_{f}^{*}}({\bar {x}})}}+1\right)+O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M{\text{Var}}_{G}(c)}{\epsilon }}+1\right)}</annotation>

</semantics>

</math><img src="./ab5e24584b134124e4067baeb778f87cf82f3304.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:69.599ex; height:7.676ex;" alt="{\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M}{1-\pi _{x_{f}^{*}}({\bar {x}})}}+1\right)+O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M{\text{Var}}_{G}(c)}{\epsilon }}+1\right)}" loading="lazy"></blockquote>where the constant factor O(1) depends only on r and L, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{Var}}_{G}(c):=\max _{x\in G}c^{T}x-\min _{x\in G}c^{T}x}">

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</munder>

<msup>

</mrow>

</msup>

</mrow>

</munder>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{Var}}_{G}(c):=\max _{x\in G}c^{T}x-\min _{x\in G}c^{T}x}</annotation>

</semantics>

</math><img src="./0c42a37ade9f2fb2623669fa6ac8f95bdffc3dec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:31.17ex; height:4.509ex;" alt="{\displaystyle {\text{Var}}_{G}(c):=\max _{x\in G}c^{T}x-\min _{x\in G}c^{T}x}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\bar {x}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\bar {x}}}</annotation>

</semantics>

</math><img src="./466e03e1c9533b4dab1b9949dad393883f385d80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:2.009ex;" alt="{\displaystyle {\bar {x}}}" loading="lazy"> is some point in the interior of G. Overall, the overall Newton complexity of finding an ε-approximate solution is at most<blockquote><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {V}{\varepsilon }}+1\right)}">

<msqrt>

</msqrt>

</mrow>

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {V}{\varepsilon }}+1\right)}</annotation>

</semantics>

</math><img src="./4e6e19be40398ebb984d16c5ed1d7aa0947bec8f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:24.468ex; height:6.176ex;" alt="{\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {V}{\varepsilon }}+1\right)}" loading="lazy">, where V is some problem-dependent constant: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V={\frac {{\text{Var}}_{G}(c)}{1-\pi _{x_{f}^{*}({\bar {x}})}}}}">

<mfrac>

<mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

<mrow>

<msub>

</mrow>

</mrow>

</msubsup>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V={\frac {{\text{Var}}_{G}(c)}{1-\pi _{x_{f}^{*}({\bar {x}})}}}}</annotation>

</semantics>

</math><img src="./762bf271ef75f0a7c086989e0805405ff0d35ad5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:15.345ex; height:7.176ex;" alt="{\displaystyle V={\frac {{\text{Var}}_{G}(c)}{1-\pi _{x_{f}^{*}({\bar {x}})}}}}" loading="lazy">.</blockquote>Each Newton step takes O(n3) arithmetic operations.

<div class="mw-heading mw-heading3"><h3 id="Initialization:_phase-I_methods">Initialization: phase-I methods</h3></div>

To initialize the path-following methods, we need a point in the relative interior of the feasible region G. In other words: if G is defined by the inequalities gi(x) ≤ 0, then we need some x for which gi(x) < 0 for all i in 1,...,m. If we do not have such a point, we need to find one using a so-called phase I method.<a href="#cite_note-:3-4">[4]</a>: 11.4 A simple phase-I method is to solve the following convex program:<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}{\text{minimize}}\quad &s\\{\text{subject to}}\quad &g_{i}(x)\leq s{\text{ for }}i=1,\dots ,m\end{aligned}}}">

<mtr>

<mtd>

<mtext>minimize</mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{minimize}}\quad &s\\{\text{subject to}}\quad &g_{i}(x)\leq s{\text{ for }}i=1,\dots ,m\end{aligned}}}</annotation>

</semantics>

</math>Denote the optimal solution by x*,s*.

<li>If s*>0, then we know that the original program is infeasible - the feasible region is empty.</li>

<li>If s*=0 and it is attained by some solution x*, then the problem is feasible but has no interior point; if it is not attained, then the problem is infeasible.</li></ul>

For this program it is easy to get an interior point: we can take arbitrarily x=0, and take s to be any number larger than max(f1(0),...,fm(0)). Therefore, it can be solved using interior-point methods. However, the run-time is proportional to log(1/s*). As s* comes near 0, it becomes harder and harder to find an exact solution to the phase-I problem, and thus harder to decide whether the original problem is feasible.

<div class="mw-heading mw-heading3"><h3 id="Practical_considerations">Practical considerations</h3></div>

The theoretic guarantees assume that the penalty parameter is increased at the rate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu =\left(1+r/{\sqrt {M}}\right)}">

<mrow>

<mrow>

</mrow>

<msqrt>

</msqrt>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu =\left(1+r/{\sqrt {M}}\right)}</annotation>

</semantics>

</math><img src="./0e77066a7e3c95b14146a108b36b2616e251ab31.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:17.222ex; height:3.343ex;" alt="{\displaystyle \mu =\left(1+r/{\sqrt {M}}\right)}" loading="lazy">, so the worst-case number of required Newton steps is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O({\sqrt {M}})}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\sqrt {M}})}</annotation>

</semantics>

</math><img src="./77017a32d5cea9a4e6bbe1df2cede0ac893f5e05.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.961ex; height:3.176ex;" alt="{\displaystyle O({\sqrt {M}})}" loading="lazy">. In theory, if μ is larger (e.g. 2 or more), then the worst-case number of required Newton steps is in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(M)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(M)}</annotation>

</semantics>

</math><img src="./b820000006cf4263aadd3475cbd522e0c4006484.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.025ex; height:2.843ex;" alt="{\displaystyle O(M)}" loading="lazy">. However, in practice, larger μ leads to a much faster convergence. These methods are called long-step methods.<a href="#cite_note-:0-3">[3]</a>: Sec.4.6 In practice, if μ is between 3 and 100, then the program converges within 20-40 Newton steps, regardless of the number of constraints (though the runtime of each Newton step of course grows with the number of constraints). The exact value of μ within this range has little effect on the performance.<a href="#cite_note-:3-4">[4]</a>: chpt.11

<div class="mw-heading mw-heading2"><h2 id="Potential-reduction_methods">Potential-reduction methods</h2></div>

For potential-reduction methods, the problem is presented in the conic form:<a href="#cite_note-:0-3">[3]</a>: Sec.5 <blockquote>minimize cTx s.t. x in {b+L} ∩ K, </blockquote>where b is a vector in Rn, L is a <a href="Linear_subspace" title="Linear subspace">linear subspace</a> in Rn (so b+L is an <a href="Affine_plane" title="Affine plane">affine plane</a>), and K is a closed pointed <a href="Convex_cone" title="Convex cone">convex cone</a> with a nonempty interior. Every convex program can be converted to the conic form. To use the potential-reduction method (specifically, the extension of <a href="Karmarkar's_algorithm" title="Karmarkar's algorithm">Karmarkar's algorithm</a> to convex programming), we need the following assumptions:<a href="#cite_note-:0-3">[3]</a>: Sec.6

<ul><li>A. The feasible set {b+L} ∩ K is bounded, and intersects the interior of the cone K.</li>

<li>B. We are given in advance a strictly-feasible solution x^, that is, a feasible solution in the interior of K.</li>

<li>C. We know in advance the optimal objective value, c*, of the problem.</li>

<li>D. We are given an M-logarithmically-homogeneous <a href="Self-concordant_barrier" class="mw-redirect" title="Self-concordant barrier">self-concordant barrier</a> F for the cone K.</li></ul>

Assumptions A, B and D are needed in most interior-point methods. Assumption C is specific to Karmarkar's approach; it can be alleviated by using a "sliding objective value". It is possible to further reduce the program to the Karmarkar format:<blockquote>minimize sTx s.t. x in M ∩ K and eTx = 1 </blockquote>where M is a <a href="Linear_subspace" title="Linear subspace">linear subspace</a> of in Rn, and the optimal objective value is 0.

The method is based on the following <a href="Scalar_potential" title="Scalar potential">scalar potential</a> function:<blockquote>v(x) = F(x) + M ln (sTx)</blockquote>where F is the M-self-concordant barrier for the feasible cone. It is possible to prove that, when x is strictly feasible and v(x) is very small (- very negative), x is approximately-optimal. The idea of the potential-reduction method is to modify x such that the potential at each iteration drops by at least a fixed constant X (specifically, X=1/3-ln(4/3)). This implies that, after i iterations, the difference between objective value and the optimal objective value is at most V * exp(-i X / M), where V is a data-dependent constant. Therefore, the number of Newton steps required for an ε-approximate solution is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)\cdot M\cdot \ln \left({\frac {V}{\varepsilon }}+1\right)+1}">

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)\cdot M\cdot \ln \left({\frac {V}{\varepsilon }}+1\right)+1}</annotation>

</semantics>

</math><img src="./c101172c40e37ba5d0adc8bc79540599f8d2f532.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:26.535ex; height:6.176ex;" alt="{\displaystyle O(1)\cdot M\cdot \ln \left({\frac {V}{\varepsilon }}+1\right)+1}" loading="lazy">.

Note that in path-following methods the expression is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\sqrt {M}}}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\sqrt {M}}}</annotation>

</semantics>

</math><img src="./83bb1f82e3f098fd52448abdd50cca4f66910ee1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.378ex; height:3.009ex;" alt="{\displaystyle {\sqrt {M}}}" loading="lazy"> rather than M, which is better in theory. But in practice, Karmarkar's method allows taking much larger steps towards the goal, so it may converge much faster than the theoretical guarantees.

<div class="mw-heading mw-heading2"><h2 id="Primal-dual_methods">Primal-dual methods</h2></div>

The primal-dual method's idea is easy to demonstrate for constrained <a href="Nonlinear_optimization" class="mw-redirect" title="Nonlinear optimization">nonlinear optimization</a>.<a href="#cite_note-9">[9]</a><a href="#cite_note-10">[10]</a> For simplicity, consider the following nonlinear optimization problem with inequality constraints:

<mtr>

<mtd>

<mi>minimize</mi>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>where</mtext>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\operatorname {minimize} \quad &f(x)\\{\text{subject to}}\quad &x\in \mathbb {R} ^{n},\\&c_{i}(x)\geq 0{\text{ for }}i=1,\ldots ,m,\\{\text{where}}\quad &f:\mathbb {R} ^{n}\to \mathbb {R} ,\ c_{i}:\mathbb {R} ^{n}\to \mathbb {R} .\end{aligned}}\quad (1)}</annotation>

</semantics>

</math>

This inequality-constrained optimization problem is solved by converting it into an unconstrained objective function whose minimum we hope to find efficiently.

Specifically, the logarithmic <a href="Barrier_function" title="Barrier function">barrier function</a> associated with (1) is

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B(x,\mu )=f(x)-\mu \sum _{i=1}^{m}\log(c_{i}(x)).\quad (2)}</annotation>

</semantics>

</math>

Here <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu }</annotation>

</semantics>

</math><img src="./9fd47b2a39f7a7856952afec1f1db72c67af6161.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mu }" loading="lazy"> is a small positive scalar, sometimes called the "barrier parameter". As <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu }</annotation>

</semantics>

</math><img src="./9fd47b2a39f7a7856952afec1f1db72c67af6161.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mu }" loading="lazy"> converges to zero the minimum of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B(x,\mu )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B(x,\mu )}</annotation>

</semantics>

</math><img src="./49955248da4386a3f342be86e8f83775f520d70b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.339ex; height:2.843ex;" alt="{\displaystyle B(x,\mu )}" loading="lazy"> should converge to a solution of (1).

The <a href="Gradient" title="Gradient">gradient</a> of a differentiable function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h:\mathbb {R} ^{n}\to \mathbb {R} }">

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h:\mathbb {R} ^{n}\to \mathbb {R} }</annotation>

</semantics>

</math><img src="./07c7c35b693abcb087f6c510903a7b67dc66197f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.465ex; height:2.343ex;" alt="{\displaystyle h:\mathbb {R} ^{n}\to \mathbb {R} }" loading="lazy"> is denoted <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \nabla h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \nabla h}</annotation>

</semantics>

</math><img src="./7fa98d91a9d33cab759480fcdef95eb3ca8da729.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.275ex; height:2.176ex;" alt="{\displaystyle \nabla h}" loading="lazy">.

The gradient of the barrier function is

</mrow>

</mrow>

</munderover>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \nabla B(x,\mu )=\nabla f(x)-\mu \sum _{i=1}^{m}{\frac {1}{c_{i}(x)}}\nabla c_{i}(x).\quad (3)}</annotation>

</semantics>

</math>

In addition to the original ("primal") variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> we introduce a <a href="Lagrange_multiplier" title="Lagrange multiplier">Lagrange multiplier</a>-inspired <a href="Lagrange_multiplier#The_strong_Lagrangian_principle:_Lagrange_duality" title="Lagrange multiplier">dual</a> variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda \in \mathbb {R} ^{m}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda \in \mathbb {R} ^{m}}</annotation>

</semantics>

</math><img src="./9159764a4cc0c68c741697818b7bf225e25625bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.549ex; height:2.343ex;" alt="{\displaystyle \lambda \in \mathbb {R} ^{m}}" loading="lazy">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i}(x)\lambda _{i}=\mu ,\quad \forall i=1,\ldots ,m.\quad (4)}</annotation>

</semantics>

</math>

Equation (4) is sometimes called the "perturbed complementarity" condition, for its resemblance to "complementary slackness" in <a href="KKT_conditions" class="mw-redirect" title="KKT conditions">KKT conditions</a>.

We try to find those <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{\mu },\lambda _{\mu })}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{\mu },\lambda _{\mu })}</annotation>

</semantics>

</math><img src="./765530433b1ef733d32f239608b33f5ca3019c90.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.975ex; height:3.009ex;" alt="{\displaystyle (x_{\mu },\lambda _{\mu })}" loading="lazy"> for which the gradient of the barrier function is zero.

Substituting <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/c_{i}(x)=\lambda _{i}/\mu }">

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/c_{i}(x)=\lambda _{i}/\mu }</annotation>

</semantics>

</math><img src="./6a757c5901e7cc841daf908b305f79e702b4d7d8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.088ex; height:2.843ex;" alt="{\displaystyle 1/c_{i}(x)=\lambda _{i}/\mu }" loading="lazy"> from (4) into (3), we get an equation for the gradient:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \nabla B(x_{\mu },\lambda _{\mu })=\nabla f(x_{\mu })-J(x_{\mu })^{T}\lambda _{\mu }=0,\quad (5)}</annotation>

</semantics>

</math>

where the matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle J}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J}</annotation>

</semantics>

</math><img src="./359e4f407b49910e02c27c2f52e87a36cd74c053.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.471ex; height:2.176ex;" alt="{\displaystyle J}" loading="lazy"> is the <a href="Jacobian_matrix_and_determinant" title="Jacobian matrix and determinant">Jacobian</a> of the constraints <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(x)}</annotation>

</semantics>

</math><img src="./b20e1deb5bbfe90c658811e9635d865f02902791.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.146ex; height:2.843ex;" alt="{\displaystyle c(x)}" loading="lazy">.

The intuition behind (5) is that the gradient of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation>

</semantics>

</math><img src="./202945cce41ecebb6f643f31d119c514bec7a074.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" loading="lazy"> should lie in the subspace spanned by the constraints' gradients. The "perturbed complementarity" with small <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu }</annotation>

</semantics>

</math><img src="./9fd47b2a39f7a7856952afec1f1db72c67af6161.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mu }" loading="lazy"> (4) can be understood as the condition that the solution should either lie near the boundary <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i}(x)=0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i}(x)=0}</annotation>

</semantics>

</math><img src="./e484952ab90e4bc58c9b6a868334c6be53c2bd4c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.206ex; height:2.843ex;" alt="{\displaystyle c_{i}(x)=0}" loading="lazy">, or that the projection of the gradient <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \nabla f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \nabla f}</annotation>

</semantics>

</math><img src="./b7b4d6de89b52c5a5e6e1583cb63eaee263e307b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.214ex; height:2.509ex;" alt="{\displaystyle \nabla f}" loading="lazy"> on the constraint component <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i}(x)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i}(x)}</annotation>

</semantics>

</math><img src="./bad0297b0dee4ae5419f9884b56352922d8cf6dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.946ex; height:2.843ex;" alt="{\displaystyle c_{i}(x)}" loading="lazy"> normal should be almost zero.

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (p_{x},p_{\lambda })}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (p_{x},p_{\lambda })}</annotation>

</semantics>

</math><img src="./595ad90da234a925b2bb63a32bcc1576634e703b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.545ex; height:2.843ex;" alt="{\displaystyle (p_{x},p_{\lambda })}" loading="lazy"> be the search direction for iteratively updating <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x,\lambda )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x,\lambda )}</annotation>

</semantics>

</math><img src="./d6f6f85d18257278b5f2dfd887d494eafb79324a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.528ex; height:2.843ex;" alt="{\displaystyle (x,\lambda )}" loading="lazy">.

Applying <a href="Newton_method" class="mw-redirect" title="Newton method">Newton's method</a> to (4) and (5), we get an equation for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (p_{x},p_{\lambda })}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (p_{x},p_{\lambda })}</annotation>

</semantics>

</math><img src="./595ad90da234a925b2bb63a32bcc1576634e703b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.545ex; height:2.843ex;" alt="{\displaystyle (p_{x},p_{\lambda })}" loading="lazy">:

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{pmatrix}H(x,\lambda )&-J(x)^{T}\\\operatorname {diag} (\lambda )J(x)&\operatorname {diag} (c(x))\end{pmatrix}}{\begin{pmatrix}p_{x}\\p_{\lambda }\end{pmatrix}}={\begin{pmatrix}-\nabla f(x)+J(x)^{T}\lambda \\\mu 1-\operatorname {diag} (c(x))\lambda \end{pmatrix}},}</annotation>

</semantics>

</math>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> is the <a href="Hessian_matrix" title="Hessian matrix">Hessian matrix</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B(x,\mu )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B(x,\mu )}</annotation>

</semantics>

</math><img src="./49955248da4386a3f342be86e8f83775f520d70b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.339ex; height:2.843ex;" alt="{\displaystyle B(x,\mu )}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {diag} (\lambda )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {diag} (\lambda )}</annotation>

</semantics>

</math><img src="./186ca22898acce8fa23e5d3ce1f273cb5134ce66.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.429ex; height:2.843ex;" alt="{\displaystyle \operatorname {diag} (\lambda )}" loading="lazy"> is a <a href="Diagonal_matrix" title="Diagonal matrix">diagonal matrix</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda }</annotation>

</semantics>

</math><img src="./b43d0ea3c9c025af1be9128e62a18fa74bedda2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.355ex; height:2.176ex;" alt="{\displaystyle \lambda }" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {diag} (c(x))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {diag} (c(x))}</annotation>

</semantics>

</math><img src="./13c130873b737f3f6b912cd049ac45ac9b8e67b6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.219ex; height:2.843ex;" alt="{\displaystyle \operatorname {diag} (c(x))}" loading="lazy"> is the diagonal matrix of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c(x)}</annotation>

</semantics>

</math><img src="./b20e1deb5bbfe90c658811e9635d865f02902791.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.146ex; height:2.843ex;" alt="{\displaystyle c(x)}" loading="lazy">.

Because of (1), (4) the condition

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda \geq 0}</annotation>

</semantics>

</math><img src="./0c26004859ae51dde7800b3f3a960c73f81cd583.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.616ex; height:2.343ex;" alt="{\displaystyle \lambda \geq 0}" loading="lazy"></dd></dl>

should be enforced at each step. This can be done by choosing appropriate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math><img src="./b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy">:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x,\lambda )\to (x+\alpha p_{x},\lambda +\alpha p_{\lambda }).}</annotation>

</semantics>

</math><img src="./6a0ff43ebec99a3741ac5e582433571f457da31c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.675ex; height:2.843ex;" alt="{\displaystyle (x,\lambda )\to (x+\alpha p_{x},\lambda +\alpha p_{\lambda }).}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Types_of_convex_programs_solvable_via_interior-point_methods">Types of convex programs solvable via interior-point methods</h2></div>

Here are some special cases of convex programs that can be solved efficiently by interior-point methods.<a href="#cite_note-:0-3">[3]</a>: Sec.10

<div class="mw-heading mw-heading3"><h3 id="Linear_programs"><a href="Linear_program" class="mw-redirect" title="Linear program">Linear programs</a></h3></div>

Consider a linear program of the form:

<mtr>

<mtd>

<mi>minimize</mi>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\operatorname {minimize} \quad &c^{\top }x\\{\text{subject to}}\quad &Ax\leq b.\end{aligned}}.}</annotation>

</semantics>

</math>

We can apply path-following methods with the barrier

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b(x):=-\sum _{j=1}^{m}\ln(b_{j}-a_{j}^{T}x).}</annotation>

</semantics>

</math>

The function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> is self-concordant with parameter M=m (the number of constraints). Therefore, the number of required Newton steps for the path-following method is O(mn2), and the total runtime complexity is O(m3/2 n2).

<div class="mw-heading mw-heading3"><h3 id="Quadratically_constrained_quadratic_programs"><a href="Quadratically_constrained_quadratic_program" title="Quadratically constrained quadratic program">Quadratically constrained quadratic programs</a></h3></div>

Given a quadratically constrained quadratic program of the form:

<mtr>

<mtd>

<mi>minimize</mi>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\operatorname {minimize} \quad &d^{\top }x\\{\text{subject to}}\quad &f_{j}(x):=x^{\top }A_{j}x+b_{j}^{\top }x+c_{j}\leq 0\quad {\text{ for all }}j=1,\dots ,m,\end{aligned}}}</annotation>

</semantics>

</math>

where all matrices Aj are <a href="Positive_semidefinite_matrices" class="mw-redirect" title="Positive semidefinite matrices">positive-semidefinite matrices</a>.

We can apply path-following methods with the barrier

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b(x):=-\sum _{j=1}^{m}\ln(-f_{j}(x)).}</annotation>

</semantics>

</math> The function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> is a self-concordant barrier with parameter M=m. The Newton complexity is O((m+n)n2), and the total runtime complexity is O(m1/2 (m+n) n2).

<div class="mw-heading mw-heading3"><h3 id="Lp_norm_approximation">Lp norm approximation</h3></div>

Consider a problem of the form

<mtr>

<mtd>

<mi>minimize</mi>

</mtd>

<mtd>

</mrow>

</munder>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\operatorname {minimize} \quad &\sum _{j}|v_{j}-u_{j}^{\top }x|_{p}\end{aligned}},}</annotation>

</semantics>

</math>

where each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u_{j}}</annotation>

</semantics>

</math><img src="./86f8d397f4684f948df846413e6d62b009718724.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.239ex; height:2.343ex;" alt="{\displaystyle u_{j}}" loading="lazy"> is a vector, each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{j}}</annotation>

</semantics>

</math><img src="./73fffa4919c0d6268f6a8d9f38c04dd3296fd0a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.037ex; height:2.343ex;" alt="{\displaystyle v_{j}}" loading="lazy"> is a scalar, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\cdot |_{p}}">

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\cdot |_{p}}</annotation>

</semantics>

</math><img src="./39f97c03851aa6215bfbb76027ea167345ea6425.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:4.032ex; height:3.176ex;" alt="{\displaystyle |\cdot |_{p}}" loading="lazy"> is an <a href="Lp_norm" class="mw-redirect" title="Lp norm">Lp norm</a> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1<p<\infty .}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1<p<\infty .}</annotation>

</semantics>

</math><img src="./2d08398e23489426d42bcc4110899e4022b338b1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.499ex; height:2.509ex;" alt="{\displaystyle 1<p<\infty .}" loading="lazy"> After converting to the standard form, we can apply path-following methods with a self-concordant barrier with parameter M=4m. The Newton complexity is O((m+n)n2), and the total runtime complexity is O(m1/2 (m+n) n2).

<div class="mw-heading mw-heading3"><h3 id="Geometric_programs"><a href="Geometric_program" class="mw-redirect" title="Geometric program">Geometric programs</a></h3></div>

Consider the problem

<mtr>

<mtd>

<mi>minimize</mi>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to</mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\operatorname {minimize} \quad &f_{0}(x):=\sum _{i=1}^{k}c_{i0}\exp(a_{i}^{\top }x)\\{\text{subject to}}\quad &f_{j}(x):=\sum _{i=1}^{k}c_{ij}\exp(a_{i}^{\top }x)\leq d_{j}\quad {\text{ for all }}j=1,\dots ,m.\end{aligned}}}</annotation>

</semantics>

</math>

There is a self-concordant barrier with parameter 2k+m. The path-following method has Newton complexity O(mk2+k3+n3) and total complexity O((k+m)1/2[mk2+k3+n3]).

<div class="mw-heading mw-heading3"><h3 id="Semidefinite_programs"><a href="Semidefinite_program" class="mw-redirect" title="Semidefinite program">Semidefinite programs</a></h3></div>

Interior point methods can be used to solve semidefinite programs.<a href="#cite_note-:0-3">[3]</a>: Sec.11

<ul><li><a href="Affine_scaling" title="Affine scaling">Affine scaling</a></li>

<li><a href="Augmented_Lagrangian_method" title="Augmented Lagrangian method">Augmented Lagrangian method</a></li>

<li><a href="Chambolle-Pock_algorithm" class="mw-redirect" title="Chambolle-Pock algorithm">Chambolle-Pock algorithm</a></li>

<li><a href="Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions" title="Karush–Kuhn–Tucker conditions">Karush–Kuhn–Tucker conditions</a></li>

<li><a href="Penalty_method" title="Penalty method">Penalty method</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFDikin1967" class="citation journal cs1">Dikin, I.I. (1967). <a rel="nofollow" class="external text" href="https://zbmath.org/?q=an:0189.19504">"Iterative solution of problems of linear and quadratic programming"</a>. Dokl. Akad. Nauk SSSR. 174 (1): 747–748. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:0189.19504">0189.19504</a>.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFKarmarkar1984" class="citation conference cs1">Karmarkar, N. (1984). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20131228145520/http://retis.sssup.it/~bini/teaching/optim2010/karmarkar.pdf">"A new polynomial-time algorithm for linear programming"</a> (PDF). Proceedings of the sixteenth annual ACM symposium on Theory of computing – STOC '84. p. 302. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F800057.808695">10.1145/800057.808695</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-89791-133-4</bdi>. Archived from <a rel="nofollow" class="external text" href="http://retis.sssup.it/~bini/teaching/optim2010/karmarkar.pdf">the original</a> (PDF) on 28 December 2013.</cite>

</li>

<li id="cite_note-:0-3">^ <a href="#cite_ref-:0_3-0">a</a> <a href="#cite_ref-:0_3-1">b</a> <a href="#cite_ref-:0_3-2">c</a> <a href="#cite_ref-:0_3-3">d</a> <a href="#cite_ref-:0_3-4">e</a> <a href="#cite_ref-:0_3-5">f</a> <a href="#cite_ref-:0_3-6">g</a> <a href="#cite_ref-:0_3-7">h</a> <a href="#cite_ref-:0_3-8">i</a> <a href="#cite_ref-:0_3-9">j</a> <a href="#cite_ref-:0_3-10">k</a> <a href="#cite_ref-:0_3-11">l</a> <a href="#cite_ref-:0_3-12">m</a> <cite id="CITEREFArkadi_Nemirovsky2004" class="citation book cs1">Arkadi Nemirovsky (2004). <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=8c3cb6395a35cb504019f87f447d65cb6cf1cdf0">Interior point polynomial-time methods in convex programming</a>.</cite>

</li>

<li id="cite_note-:3-4">^ <a href="#cite_ref-:3_4-0">a</a> <a href="#cite_ref-:3_4-1">b</a> <a href="#cite_ref-:3_4-2">c</a> <cite id="CITEREFBoydVandenberghe2004" class="citation book cs1">Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge: <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-83378-3</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2061575">2061575</a>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFWright2004" class="citation journal cs1">Wright, Margaret H. (2004). <a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0273-0979-04-01040-7">"The interior-point revolution in optimization: History, recent developments, and lasting consequences"</a>. Bulletin of the American Mathematical Society. 42: 39–57. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0273-0979-04-01040-7">10.1090/S0273-0979-04-01040-7</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2115066">2115066</a>.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFPotraStephen_J._Wright2000" class="citation journal cs1">Potra, Florian A.; Stephen J. Wright (2000). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0377-0427%2800%2900433-7">"Interior-point methods"</a>. Journal of Computational and Applied Mathematics. 124 (1–2): 281–302. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2000JCoAM.124..281P">2000JCoAM.124..281P</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0377-0427%2800%2900433-7">10.1016/S0377-0427(00)00433-7</a>.</cite>

</li>

<li id="cite_note-:1-7">^ <a href="#cite_ref-:1_7-0">a</a> <a href="#cite_ref-:1_7-1">b</a> <cite id="CITEREFRenegar1988" class="citation journal cs1">Renegar, James (1 January 1988). <a rel="nofollow" class="external text" href="https://doi.org/10.1007/BF01580724">"A polynomial-time algorithm, based on Newton's method, for linear programming"</a>. Mathematical Programming. 40 (1): 59–93. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01580724">10.1007/BF01580724</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1436-4646">1436-4646</a>.</cite>

</li>

<li id="cite_note-:2-8">^ <a href="#cite_ref-:2_8-0">a</a> <a href="#cite_ref-:2_8-1">b</a> <cite id="CITEREFGonzaga1989" class="citation cs2">Gonzaga, Clovis C. (1989), Megiddo, Nimrod (ed.), <a rel="nofollow" class="external text" href="https://doi.org/10.1007/978-1-4613-9617-8_1">"An Algorithm for Solving Linear Programming Problems in O(n3L) Operations"</a>, Progress in Mathematical Programming: Interior-Point and Related Methods, New York, NY: Springer, pp. 1–28, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-1-4613-9617-8_1">10.1007/978-1-4613-9617-8_1</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4613-9617-8</bdi>, retrieved 22 November 2023</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFMehrotra1992" class="citation journal cs1">Mehrotra, Sanjay (1992). "On the Implementation of a Primal-Dual Interior Point Method". SIAM Journal on Optimization. 2 (4): 575–601. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0802028">10.1137/0802028</a>.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFWright1997" class="citation book cs1">Wright, Stephen (1997). Primal-Dual Interior-Point Methods. Philadelphia, PA: SIAM. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-89871-382-4</bdi>.</cite>

</li>

</ol></div></div>

<ul><li><cite id="CITEREFBonnansGilbertLemaréchalSagastizábal2006" class="citation book cs1">Bonnans, J. Frédéric; Gilbert, J. Charles; <a href="Claude_Lemar%C3%A9chal" title="Claude Lemaréchal">Lemaréchal, Claude</a>; <a href="Claudia_Sagastiz%C3%A1bal" title="Claudia Sagastizábal">Sagastizábal, Claudia A.</a> (2006). <a rel="nofollow" class="external text" href="https://www.springer.com/mathematics/applications/book/978-3-540-35445-1">Numerical optimization: Theoretical and practical aspects</a>. Universitext (Second revised ed. of translation of 1997 French ed.). Berlin: Springer-Verlag. pp. xiv+490. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-35447-5">10.1007/978-3-540-35447-5</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-35445-1</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2265882">2265882</a>.</cite></li>

<li><cite id="CITEREFNocedalStephen_Wright1999" class="citation book cs1">Nocedal, Jorge; Stephen Wright (1999). Numerical Optimization. New York, NY: Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-98793-4</bdi>.</cite></li>

<li><cite id="CITEREFPressTeukolskyVetterlingFlannery2007" class="citation book cs1">Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110811154417/http://apps.nrbook.com/empanel/index.html#pg=537">"Section 10.11. Linear Programming: Interior-Point Methods"</a>. Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-88068-8</bdi>. Archived from <a rel="nofollow" class="external text" href="http://apps.nrbook.com/empanel/index.html#pg=537">the original</a> on 11 August 2011. Retrieved 12 August 2011.</cite></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Optimization:_Algorithms,_methods,_and_heuristics381" style="padding:3px"><table class="nowraplinks hlist mw-collapsible uncollapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="3"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Optimization:_Algorithms,_methods,_and_heuristics381" style="font-size:114%;margin:0 4em"><a href="Mathematical_optimization" title="Mathematical optimization">Optimization</a>: <a href="Optimization_algorithm" class="mw-redirect" title="Optimization algorithm">Algorithms</a>, <a href="Iterative_method" title="Iterative method">methods</a>, and <a href="Heuristic_algorithm" class="mw-redirect" title="Heuristic algorithm">heuristics</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Unconstrained_nonlinear381" style="font-size:114%;margin:0 4em"><a href="Nonlinear_programming" title="Nonlinear programming">Unconstrained nonlinear</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Function_(mathematics)" title="Function (mathematics)">Functions</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Golden-section_search" title="Golden-section search">Golden-section search</a></li>

<li><a href="Powell's_method" title="Powell's method">Powell's method</a></li>

<li><a href="Line_search" title="Line search">Line search</a></li>

<li><a href="Nelder%E2%80%93Mead_method" title="Nelder–Mead method">Nelder–Mead method</a></li>

<li><a href="Successive_parabolic_interpolation" title="Successive parabolic interpolation">Successive parabolic interpolation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Gradient" title="Gradient">Gradients</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Local_convergence" title="Local convergence">Convergence</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Trust_region" title="Trust region">Trust region</a></li>

<li><a href="Wolfe_conditions" title="Wolfe conditions">Wolfe conditions</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quasi-Newton_method" title="Quasi-Newton method">Quasi–Newton</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Berndt%E2%80%93Hall%E2%80%93Hall%E2%80%93Hausman_algorithm" title="Berndt–Hall–Hall–Hausman algorithm">Berndt–Hall–Hall–Hausman</a></li>

<li><a href="Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm" title="Broyden–Fletcher–Goldfarb–Shanno algorithm">Broyden–Fletcher–Goldfarb–Shanno</a> and <a href="Limited-memory_BFGS" title="Limited-memory BFGS">L-BFGS</a></li>

<li><a href="Davidon%E2%80%93Fletcher%E2%80%93Powell_formula" title="Davidon–Fletcher–Powell formula">Davidon–Fletcher–Powell</a></li>

<li><a href="Symmetric_rank-one" title="Symmetric rank-one">Symmetric rank-one (SR1)</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Iterative_method" title="Iterative method">Other methods</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Nonlinear_conjugate_gradient_method" title="Nonlinear conjugate gradient method">Conjugate gradient</a></li>

<li><a href="Gauss%E2%80%93Newton_algorithm" title="Gauss–Newton algorithm">Gauss–Newton</a></li>

<li><a href="Gradient_descent" title="Gradient descent">Gradient</a></li>

<li><a href="Mirror_descent" title="Mirror descent">Mirror</a></li>

<li><a href="Levenberg%E2%80%93Marquardt_algorithm" title="Levenberg–Marquardt algorithm">Levenberg–Marquardt</a></li>

<li><a href="Powell's_dog_leg_method" title="Powell's dog leg method">Powell's dog leg method</a></li>

<li><a href="Truncated_Newton_method" title="Truncated Newton method">Truncated Newton</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Hessian_matrix" title="Hessian matrix">Hessians</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Newton's_method_in_optimization" title="Newton's method in optimization">Newton's method</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td><td class="noviewer navbox-image" rowspan="5" style="width:1px;padding:0 0 0 2px"><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Constrained_nonlinear381" style="font-size:114%;margin:0 4em"><a href="Nonlinear_programming" title="Nonlinear programming">Constrained nonlinear</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Barrier_function" title="Barrier function">Barrier methods</a></li>

<li><a href="Penalty_method" title="Penalty method">Penalty methods</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Differentiable</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Augmented_Lagrangian_method" title="Augmented Lagrangian method">Augmented Lagrangian methods</a></li>

<li><a href="Sequential_quadratic_programming" title="Sequential quadratic programming">Sequential quadratic programming</a></li>

<li><a href="Successive_linear_programming" title="Successive linear programming">Successive linear programming</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible uncollapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Convex_optimization381" style="font-size:114%;margin:0 4em"><a href="Convex_optimization" title="Convex optimization">Convex optimization</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Convex_minimization" class="mw-redirect" title="Convex minimization">Convex minimization</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Cutting-plane_method" title="Cutting-plane method">Cutting-plane method</a></li>

<li><a href="Frank%E2%80%93Wolfe_algorithm" title="Frank–Wolfe algorithm">Reduced gradient (Frank–Wolfe)</a></li>

<li><a href="Subgradient_method" title="Subgradient method">Subgradient method</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Linear_programming" title="Linear programming">Linear</a> and <a href="Quadratic_programming" title="Quadratic programming">quadratic</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Linear_programming#Interior_point" title="Linear programming">Interior point</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Affine_scaling" title="Affine scaling">Affine scaling</a></li>

<li><a href="Ellipsoid_method" title="Ellipsoid method">Ellipsoid algorithm of Khachiyan</a></li>

<li><a href="Karmarkar's_algorithm" title="Karmarkar's algorithm">Projective algorithm of Karmarkar</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Matroid" title="Matroid">Basis-</a><a href="Exchange_algorithm" class="mw-redirect" title="Exchange algorithm">exchange</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Simplex_algorithm" title="Simplex algorithm">Simplex algorithm of Dantzig</a></li>

<li><a href="Revised_simplex_method" title="Revised simplex method">Revised simplex algorithm</a></li>

<li><a href="Criss-cross_algorithm" title="Criss-cross algorithm">Criss-cross algorithm</a></li>

<li><a href="Lemke's_algorithm" title="Lemke's algorithm">Principal pivoting algorithm of Lemke</a></li>

<li><a href="Active-set_method" title="Active-set method">Active-set method</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Combinatorial381" style="font-size:114%;margin:0 4em"><a href="Combinatorial_optimization" title="Combinatorial optimization">Combinatorial</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Paradigms</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Approximation_algorithm" title="Approximation algorithm">Approximation algorithm</a></li>

<li><a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a></li>

<li><a href="Greedy_algorithm" title="Greedy algorithm">Greedy algorithm</a></li>

<li><a href="Integer_programming" title="Integer programming">Integer programming</a>

<ul><li><a href="Branch_and_bound" title="Branch and bound">Branch and bound</a>/<a href="Branch_and_cut" title="Branch and cut">cut</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Graph_algorithm" class="mw-redirect" title="Graph algorithm">Graph algorithms</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Minimum_spanning_tree52" scope="row" class="navbox-group" style="width:1%"><a href="Minimum_spanning_tree" title="Minimum spanning tree">Minimum spanning tree</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bor%C5%AFvka's_algorithm" title="Borůvka's algorithm">Borůvka</a></li>

<li><a href="Kruskal's_algorithm" title="Kruskal's algorithm">Kruskal</a></li></ul>

</div></td></tr></tbody></table><div>

</div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Shortest_path39" scope="row" class="navbox-group" style="width:1%"><a href="Shortest_path_problem" title="Shortest path problem">Shortest path</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bellman%E2%80%93Ford_algorithm" title="Bellman–Ford algorithm">Bellman–Ford</a>

<li><a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra</a></li>

<li><a href="Floyd%E2%80%93Warshall_algorithm" title="Floyd–Warshall algorithm">Floyd–Warshall</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Flow_network" title="Flow network">Network flows</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Dinic's_algorithm" title="Dinic's algorithm">Dinic</a></li>

<li><a href="Edmonds%E2%80%93Karp_algorithm" title="Edmonds–Karp algorithm">Edmonds–Karp</a></li>

<li><a href="Ford%E2%80%93Fulkerson_algorithm" title="Ford–Fulkerson algorithm">Ford–Fulkerson</a></li>

<li><a href="Push%E2%80%93relabel_maximum_flow_algorithm" title="Push–relabel maximum flow algorithm">Push–relabel maximum flow</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Metaheuristics381" style="font-size:114%;margin:0 4em"><a href="Metaheuristic" title="Metaheuristic">Metaheuristics</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Evolutionary_algorithm" title="Evolutionary algorithm">Evolutionary algorithm</a></li>

<li><a href="Hill_climbing" title="Hill climbing">Hill climbing</a></li>

<li><a href="Local_search_(optimization)" title="Local search (optimization)">Local search</a></li>

<li><a href="Parallel_metaheuristic" title="Parallel metaheuristic">Parallel metaheuristics</a></li>

<li><a href="Simulated_annealing" title="Simulated annealing">Simulated annealing</a></li>

<li><a href="Spiral_optimization_algorithm" title="Spiral optimization algorithm">Spiral optimization algorithm</a></li>

<li><a href="Tabu_search" title="Tabu search">Tabu search</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><td class="navbox-abovebelow" colspan="3"><div>

<ul><li><a href="Comparison_of_optimization_software" title="Comparison of optimization software">Software</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-20" href="https://en.wikipedia.org/wiki/?title=Interior-point_method&oldid=1296435256">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>